lib/Mi manual de algoritmos/version_actual/src/number_theory/criba.cpp

   1 const int SIZE = 1000000;
   2
   3 //criba[i] = false si i es primo
   4 bool criba[SIZE+1];
   5
   6 void buildCriba(){
   7   memset(criba, false, sizeof(criba));
   8
   9   criba[0] = criba[1] = true;
  10   for (int i=4; i<=SIZE; i += 2){
  11     criba[i] = true;
  12   }
  13   for (int i=3; i*i<=SIZE; i += 2){
  14     if (!criba[i]){
  15       for (int j=i*i; j<=SIZE; j += i){
  16         criba[j] = true;
  17       }
  18     }
  19   }
  20 }